#ifndef HERM_BASE_ALLOCATOR_H
#define HERM_BASE_ALLOCATOR_H

#ifdef __linux__
#include <ext/pool_allocator.h>
#endif // end #ifdef __linux__
#include <vector>
#include <memory>
#include <limits>
#include "herm/base/utils/misc.h"
#include "private/list.h"

namespace herm{

/**
 * @brief Wrap __gnu_cxx::pool_alloc in linux and std::allocator in Windows.
 */
#ifdef __linux__
	template <class T>
	class LiteAllocator : public __gnu_cxx::__pool_alloc<T>
	{
	public:
		T* Malloc() 
		{
			T* ptr = __gnu_cxx::__pool_alloc<T>::allocate(1);
			::new (ptr) T;

			return ptr;
		}

		template <class P>
		T* Malloc(P& p)
		{
			T* ptr = __gnu_cxx::__pool_alloc<T>::allocate(1);
			::new (ptr) T(p);

			return ptr;

		}

		void Free(T* ptr)
		{
			__gnu_cxx::__pool_alloc<T>::destroy(ptr);
			__gnu_cxx::__pool_alloc<T>::deallocate(ptr, 1);
		}
	};
#else 
    template <class T>
	class LiteAllocator 
	{
	public:
		T* Malloc() 
		{
			return new T;
		}
        
		template <class P>
		T* Malloc(P& p)
		{
            return T(p);
		}
        
		void Free(T* ptr)
		{
            delete ptr;
		}
	};
#endif // end #ifdef __linux__

static const int INVALID_IDX = (std::numeric_limits<int>::max)();

class IdxList
{
public:	
	struct IdxNode
	{
		unsigned int used : 1;
		unsigned int preIdx : 31;  // 31bit is 0, free; is 1, used
		int nextIdx;
	};

	IdxList()
	{
		m_idxs = nullptr;
		m_headIdx = INVALID_IDX;
	}

	IdxList(std::vector<IdxNode>* idxs)
	{
		m_idxs = idxs;
		m_headIdx = INVALID_IDX;
	}

	void PushFront(int idx)
	{
		(*m_idxs)[idx].preIdx = INVALID_IDX;
		(*m_idxs)[idx].nextIdx = m_headIdx;
		m_headIdx = idx;
	}

	int PopFront()
	{
		if (m_headIdx == INVALID_IDX)
			return INVALID_IDX;

		int idx = m_headIdx;
		m_headIdx = (*m_idxs)[idx].nextIdx;
		if (m_headIdx != INVALID_IDX)
		{
			(*m_idxs)[m_headIdx].preIdx = INVALID_IDX;
		}

		return idx;
	}

	void Erase(int idx)
	{
		if (m_headIdx == INVALID_IDX)
			return;

		int preIdx = (*m_idxs)[idx].preIdx;
		int nextIdx = (*m_idxs)[idx].nextIdx;

		if (preIdx == INVALID_IDX) // head node, include one node
		{
			m_headIdx = nextIdx; 
		}
		else if (nextIdx == INVALID_IDX) // tail node and preIdx != INVALID_IDX
		{
			(*m_idxs)[preIdx].nextIdx = INVALID_IDX;
		}
		else 
		{
			(*m_idxs)[preIdx].nextIdx = nextIdx;
			(*m_idxs)[nextIdx].preIdx = preIdx;
		}
	}
private:
	std::vector<IdxNode>* m_idxs;
	int m_headIdx;     // free index list
};

template<class T>
struct AllocatorBase
{	
    typedef T value_type;
};

// TEMPLATE CLASS _Allocator_base<const _Ty>
template<class T>
struct AllocatorBase<const T>
{
    typedef T value_type;
};
/**
 * @brief stl allocator for large object(>120bytes). 
 * The small object must use LiteAllocator!
 */

template <class T>
class Allocator : public std::allocator<T>
{
public:
	T* Malloc() 
	{
		T* ptr = std::allocator<T>::allocate(1);
		::new (ptr) T();

		return ptr;
	}

	template <class P>
	T* Malloc(P& p)
	{
		T* ptr = std::allocator<T>::allocate(1);
		::new (ptr) T(p);

		return ptr;

	}

	void Free(T* ptr)
	{
		destroy(ptr);
		deallocate(ptr, 1);
	}
};

/*
template <class T>
class Allocator
{
public:
    typedef AllocatorBase<T> Mybase;
    typedef typename Mybase::value_type value_type;
	typedef size_t     size_type;
	typedef ptrdiff_t  difference_type;
	typedef value_type*       pointer;
	typedef const value_type* const_pointer;
	typedef value_type&       reference;
	typedef const value_type& const_reference;

	template<class _Other>
	struct rebind
	{	// convert an allocator<_Ty> to an allocator <_Other>
		typedef Allocator<_Other> other;
	};

	Allocator()
	{
		m_objs = nullptr;
	}

	Allocator(int size) : m_freeIdxs(&m_idxs), m_usedIdxs(&m_idxs)
	{
		HERM_ASSERT(size < (std::numeric_limits<int>::max)() / 2);

		m_objs = (pointer)::operator new(size * sizeof(T));
        m_idxs.resize(size);

		for (int i = (int)m_idxs.size() - 1; i >= 0; i--)
		{
			m_idxs[i].used = 0;
			m_freeIdxs.PushFront(i);
		}
	}

	Allocator(const Allocator&){}
	template <class T1>
	Allocator(const Allocator<T1>&) {}

	~Allocator()
	{
		delete m_objs;
    }

	pointer allocate(size_t count = 1)
	{
		(void)count;
		int idx = AllocateIdx();
		return GetObj(idx);
	}

	void construct(pointer buf, const T& val)
	{
		::new(buf) T(val); 
	}

	void deallocate(pointer ptr, size_type)
	{
		int idx = (int)(ptr - m_objs);
		DeallocateByIdx(idx);
	}

	void destroy(pointer ptr)
	{
		ptr->~T();
	}

	size_t max_size() const
	{	// estimate maximum array size
		return m_idxs.size();
	}

	pointer Malloc()
	{
		pointer ptr = allocate();
		if (!ptr)
			return nullptr;

		::new (ptr) T; 

		return ptr;
	}

	template <class P>
	T* Malloc(P& p)
	{
		pointer ptr = allocate();
		if (!ptr)
			return nullptr;

		::new (ptr) T(p); 

		return ptr;
	}

	void Free(pointer ptr)
	{
		destroy(ptr);
		deallocate(ptr, 1);
	}

	T* GetObj(int idx)
	{
		if (idx < 0 || idx >= (int)m_idxs.size())
			return nullptr;

		if (m_idxs[idx].used == 0)
			return nullptr;

		return &m_objs[idx];
	}

	int AllocateIdx()
	{
		// Pop a free index from the free index list
		int idx = m_freeIdxs.PopFront();
		if (idx == INVALID_IDX)
			return INVALID_IDX;

		m_idxs[idx].used = 1;

		// Push this index to the used index list
		m_usedIdxs.PushFront(idx);

		return idx;
	}

	int GetCapacity() const
	{
		return (int)m_idxs.size();
	}

private:
	void DeallocateByIdx(int idx)
	{
		if (idx > (int)m_idxs.size() || idx < 0)
			return;

		if (m_idxs[idx].used == 0)
			return;

		m_idxs[idx].used = 0;

		// Pop idx from the used list
		m_usedIdxs.Erase(idx);

		// Push idx to the free list
		m_freeIdxs.PushFront(idx);
	}
private:
	pointer m_objs;
	std::vector<IdxList::IdxNode> m_idxs;
	IdxList m_freeIdxs; // free index list
	IdxList m_usedIdxs; // used index list
};

template<class T, class Other> 
inline bool operator==(const Allocator<T>&, const Allocator<Other>&) 
{	// test for allocator equality (always true)
    return true;
}

template<class T, class Other> 
inline bool operator!=(const Allocator<T>&, const Allocator<Other>&) 
{	// test for allocator equality (always true)
    return false;
}*/
} // end namespace herm{

#endif // end #ifndef HERM_BASE_ALLOCATOR_H
